'''
给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

 

示例：
二叉树：[3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
'''
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root: return []
        # 跟结点入queue
        queue = [root]
        res = []
        while queue:
            res.append([node.val for node in queue])
            # 存储当前层的孩子节点列表
            ll = []
            # 对当前层的每个节点遍历
            for node in queue:
                # 如果左子节点存在，入队列
                if node.left:
                    ll.append(node.left)
                # 如果右子节点存在，入队列
                if node.right:
                    ll.append(node.right)
            # 后把queue更新成下一层的结点，继续遍历下一层
            queue = ll
        return res
